/*
 * @lc app=leetcode.cn id=380 lang=cpp
 * @lcpr version=30204
 *
 * [380] O(1) 时间插入、删除和获取随机元素
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class RandomizedSet
{
private:
    unordered_map<int, int> valToIndex; // 存储元素及其索引
    vector<int> values;                 // 存储元素
public:
    RandomizedSet()
    {
    }

    bool insert(int val)
    {
        if (valToIndex.count(val)) {
            return false; // 元素已存在
        }
        values.push_back(val); // 插入到 vector 的末尾
        valToIndex[val] = values.size() - 1; // 记录元素的索引
        return true;
    }

    bool remove(int val)
    {
        if (!valToIndex.count(val)) {
            return false; // 元素不存在
        }
        int index = valToIndex[val]; // 获取元素的索引
        int lastVal = values.back(); // 获取 vector 的最后一个元素

        // 将最后一个元素移动到要删除元素的位置
        values[index] = lastVal;
        valToIndex[lastVal] = index;

        // 删除最后一个元素
        values.pop_back();
        valToIndex.erase(val); // 从 map 中移除元素
        return true;
    }

    int getRandom()
    {
        int randomIndex = rand() % values.size(); // 生成随机索引
        return values[randomIndex]; // 返回随机元素
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
// @lc code=end
